package _3sort.src;

public class _3insertSort {
    //相对来说优于选择和冒泡排序，最差复杂度为O（n2)
    public static void main(String[] args) {
        int[] nums = {5, 8, 5, 6, 4, 8, 3, 41, 1};
        insert(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }

    public static void insert(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = 1; i < nums.length; i++) {
            //从索引为1开始，因为索引0只有一个值，不存在排序
            for (int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
                //j >= 0 && nums[j] > nums[j + 1]判断前后大小关系
                //若是nums[j]< nums[j + 1],直接可以跳出循环，否则一直排序直至拍到最开始的索引处
                swaq(nums, j, j + 1);
            }
        }
    }

    public static void swaq(int[] nums, int i, int j) {
        nums[i]=nums[i]^nums[j];
        nums[j]=nums[i]^nums[j];
        nums[i]=nums[i]^nums[j];
    }
}
